package com.samxcode.leetcode;

/**
 * Implement strStr().
 * 
 * Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of
 * haystack.
 * 
 * Solution: KMP or Boyer-More algorithm reference: http://blog.jobbole.com/52830/
 * 
 * @author Sam
 *
 */
public class ImplementStrStr {

    public static void main(String[] args) {
        System.out.println(strStr("a", ""));
    }


    /* boyer-Moore algorithm */
    public static int strStr(String haystack, String needle) {
        char[] needles = needle.toCharArray();
        int hl = haystack.length();
        int l = needles.length;
        if (l > hl) {
            return -1;
        }
        if (l == 0) {
            return 0;
        }
        int i = 0, j = 0;
        int[] bmbc = new int[256];
        int[] suffix = new int[l];
        int[] bmgs = new int[l];
        bmBc(needles, l, bmbc);
        suffix(needles, l, suffix);
        bmGs(needles, l, bmgs);
        while (j <= hl - l) {
            for (i = l - 1; i >= 0 && needles[i] == haystack.charAt(i + j); i--);
            if (i < 0) {
                return j;
            } else {
                j += Math.max(bmbc[haystack.charAt(i + j)] - l + 1 + i, bmgs[i]);
            }
        }
        return -1;
    }


    private static void bmBc(char[] needles, int l, int[] bmbc) {
        int i = 0;
        for (i = 0; i < bmbc.length; i++) {
            bmbc[i] = l;
        }
        for (i = 0; i < l - 1; i++) {
            bmbc[needles[i]] = l - 1 - i;
        }
    }


    private static void bmGs(char[] needles, int l, int[] bmgs) {
        int i = 0, j;
        int[] suffix = new int[l];
        suffix(needles, l, suffix);
        // no good suffix
        for (i = 0; i < l; i++) {
            bmgs[i] = l;
        }
        // part good suffix
        j = 0;
        for (i = l - 2; i >= 0; i--) {
            if (suffix[i] == i + 1) {
                while (j < l - 1 - i) {
                    if (bmgs[i] == l) {
                        bmgs[i] = l - 1 - i;
                    }
                    j++;
                }
            }
        }
        // full good suffix
        for (i = 0; i < l - 1; i++) {
            bmgs[l - 1 - suffix[i]] = l - 1 - i;
        }
    }


    // build suffix
    private static void suffix(char[] needles, int l, int[] suffix) {
        int s, e, i;
        suffix[l - 1] = l;
        s = l - 1;
        e = l - 1;
        for (i = l - 2; i >= 0; i--) {
            if (e < i && suffix[l - 1 - s + i] < i - e) {
                suffix[i] = suffix[l - 1 - s + i];
            } else {
                s = i;
                e = i;
                while (e >= 0 && needles[e] == needles[l - 1 - s + e]) {
                    --e;
                }
                suffix[i] = s - e;
            }
        }
    }
}